﻿using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.GamerServices;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework.Media;
using Microsoft.Xna.Framework.Net;
using Microsoft.Xna.Framework.Storage;

using ProceduralGolf.geometry;
using ProceduralGolf.generation;
using System.Collections;

namespace ProceduralGolf.terrain
{
    class BinaryTriangleTree
    {
        int width;
        int height;

        VarianceTree varianceTree;

        public BinaryTriangle LeftRoot { get { return leftRoot; } }
        public BinaryTriangle RightRoot { get { return rightRoot; } }

        BinaryTriangle leftRoot;
        BinaryTriangle rightRoot;

        int nVertices;
        VertexBuffer vertexBuffer;
        //IDictionary<GolfCourseLayout.GolfCourseLayer,int> nIndices;
        //IDictionary<GolfCourseLayout.GolfCourseLayer,IndexBuffer> indexBuffers;

        //int[] nIndices;
        //IndexBuffer[] indexBuffers;

        ////IDictionary<GolfCourseLayout.GolfCourseLayer, Effect> effects;
        //Effect[] effects;

        int nIndices;
        IndexBuffer indexBuffer;

        Effect effect;

        float offsetX;
        float offsetY;

        float scale;

        Vector3[,] normalmap;

        VertexDeclaration vertexDeclaration = null;

        public BinaryTriangleTree(Heightmap heightmap) : this(heightmap, 1.0f, 0.0f, 0.0f) { }

        public BinaryTriangleTree(Heightmap heightmap, float scale, float offsetX, float offsetY)
        {
            this.scale = scale;
            width = heightmap.Width;
            height = heightmap.Height;
            varianceTree = new VarianceTree(heightmap);

            leftRoot = rightRoot = null;
            this.offsetX = offsetX;
            this.offsetY = offsetY;

            //effects = new Dictionary<GolfCourseLayout.GolfCourseLayer, Effect>();
            //effects = new Effect[GolfCourseLayout.LayerCount];
        }

        ~BinaryTriangleTree()
        {
            vertexBuffer.Dispose();
            indexBuffer.Dispose();
        }

        public float GetHeight(int x, int y)
        {
            BinaryTriangle triangle = GetTriangle(x, y);
            if (triangle == null)
                return 0;
            else
                return triangle.Triangle.GetHeight(x, y, varianceTree.Heightmap);
        }

        BinaryTriangle GetTriangle(int x, int y)
        {
            if (leftRoot == null || rightRoot == null)
                return null;

            if (leftRoot.Triangle.InTriangle(x, y))
                return leftRoot.GetTriangle(x, y);
            else
                return rightRoot.GetTriangle(x, y);
        }

        public void SetNormalMap(Vector3[,] normalmap)
        {
            this.normalmap = normalmap;
        }

        //public void AddEffect(Effect effect, GolfCourseLayout.GolfCourseLayer layer)
        //{
        //    effects[(int)layer] = effect;
        //}

        public void SetEffect(Effect effect)
        {
            this.effect = effect;
        }

        public void GenerateRoot()
        {
            leftRoot = new BinaryTriangle(varianceTree.LeftRoot);
            rightRoot = new BinaryTriangle(varianceTree.RightRoot);

            leftRoot.BaseNeighbor = rightRoot;
            rightRoot.BaseNeighbor = leftRoot;

            //leftRoot.Tree = varianceTree;
            //rightRoot.Tree = varianceTree;
        }

        public void Generate(float maxVariance, Vector3 cameraPosition)
        {
            if (leftRoot == null || rightRoot == null)
            {
                GenerateRoot();
            }

            RecursiveSplit(leftRoot, maxVariance, cameraPosition);
            RecursiveSplit(rightRoot, maxVariance, cameraPosition);
        }

        bool[] UsedVertices()
        {
            int[] indices = Indices();
            bool[] vertices = new bool[width * height];
            foreach (int i in indices)
            {
                vertices[i] = true;
            }
            return vertices;
        }

        int[] UsedVertexIndices()
        {
            bool[] verts = UsedVertices();
            int[] indices = new int[verts.Length];
            int idx = 0;
            int usedIdx = 0;
            while (idx < verts.Length)
            {
                if (verts[idx])
                {
                    indices[idx] = usedIdx;
                    ++usedIdx;
                }
                else
                {
                    indices[idx] = -1;
                }
                ++idx;
            }
            return indices;
        }

        //public void GenerateBuffers(GraphicsDevice graphicsDevice)
        //{
        //    VertexPositionNormal[] vertices = Vertices();
        //    int[] usedVertexIndices = UsedVertexIndices();
        //    for (int i = 0; i < usedVertexIndices.Length; ++i)
        //    {
        //        int idx = usedVertexIndices[i];
        //        if (idx != -1)
        //        {
        //            int x = i % width;
        //            int y = i / width;
        //            vertices[idx].Normal = normalmap[x, y];
        //        }
        //    }

        //    //for (int x = 0; x < width; ++x)
        //    //{
        //    //    for (int y = 0; y < height; ++y)
        //    //    {
        //    //        vertices[Coordinate2Index(x, y)].Normal = normalmap[x, y];
        //    //    }
        //    //}

        //    nVertices = vertices.Length;
        //    vertexBuffer = new VertexBuffer(graphicsDevice, typeof(VertexPositionNormal), nVertices, BufferUsage.WriteOnly);
        //    vertexBuffer.SetData(vertices);
            
        //    //nIndices = new Dictionary<GolfCourseLayout.GolfCourseLayer, int>();
        //    //indexBuffers = new Dictionary<GolfCourseLayout.GolfCourseLayer, IndexBuffer>();

        //    nIndices = new int[GolfCourseLayout.LayerCount];
        //    indexBuffers = new IndexBuffer[GolfCourseLayout.LayerCount];

        //    IDictionary<GolfCourseLayout.GolfCourseLayer, int[]> indices = LayerIndices();

        //    foreach (KeyValuePair<GolfCourseLayout.GolfCourseLayer, int[]> kv in indices)
        //    {
        //        GolfCourseLayout.GolfCourseLayer layer = kv.Key;
        //        int[] ids = kv.Value;

        //        nIndices[(int)layer] = ids.Length;
        //        if (nIndices[(int)layer] > 0)
        //        {
        //            indexBuffers[(int)layer] = new IndexBuffer(graphicsDevice, typeof(int), nIndices[(int)layer], BufferUsage.WriteOnly);
        //            indexBuffers[(int)layer].SetData(ids);
        //        }
        //    }

        //    // free resources: we dont need variance tree anymore
        //    varianceTree = null;
        //    GC.Collect();
        //}

        public void GenerateBuffers(GraphicsDevice graphicsDevice)
        {
            VertexPositionNormal[] vertices = VerticesCompressed();
            int[] indices = IndicesCompressed();

            int[] usedVertexIndices = UsedVertexIndices();
            for (int i = 0; i < usedVertexIndices.Length; ++i)
            {
                int idx = usedVertexIndices[i];
                if (idx != -1)
                {
                    int x = i % width;
                    int y = i / width;
                    vertices[idx].Normal = normalmap[x, y];
                }
            }

            //for (int x = 0; x < width; ++x)
            //{
            //    for (int y = 0; y < height; ++y)
            //    {
            //        vertices[Coordinate2Index(x, y)].Normal = normalmap[x, y];
            //    }
            //}

            nVertices = vertices.Length;
            vertexBuffer = new VertexBuffer(graphicsDevice, typeof(VertexPositionNormal), nVertices, BufferUsage.WriteOnly);
            vertexBuffer.SetData(vertices);
            

            nIndices = indices.Length;
            indexBuffer = new IndexBuffer(graphicsDevice, typeof(int), nIndices, BufferUsage.WriteOnly);
            indexBuffer.SetData(indices);

            // free resources: we dont need variance tree anymore
            varianceTree = null;
            GC.Collect();
        }

        public int CountTriangles()
        {
            if (leftRoot == null)
            {
                return 0;
            }
            else
            {
                return leftRoot.CountTriangles() + rightRoot.CountTriangles();
            }
        }
        #region Split triangles
        void RecursiveSplit(BinaryTriangle triangle, float maxVariance, Vector3 cameraPosition)
        {
            float distance = 1.0f; // TODO: calc real distance
            //float variance = triangle.Variance() / distance;
            float variance = varianceTree.Variance(triangle.Triangle) / distance;
            if (!triangle.IsLeaf() && variance > maxVariance)
            {
                Split(triangle);
                RecursiveSplit(triangle.LeftChild, maxVariance, cameraPosition);
                RecursiveSplit(triangle.RightChild, maxVariance, cameraPosition);
            }
        }

        void Split(BinaryTriangle triangle)
        {
            if (triangle.IsSplit())
            {
                return;
            }

            if (triangle.BaseNeighbor == null)
            {
                // at edge: just split triangle
                RealSplit(triangle);
            }
            else
            {
                if (triangle.BaseNeighbor.BaseNeighbor != triangle)
                {
                    // not a diamond: force split base neighbor
                    Split(triangle.BaseNeighbor);
                }

                // split diamond
                RealSplit(triangle);
                RealSplit(triangle.BaseNeighbor);

                triangle.LeftChild.RightNeighbor = triangle.BaseNeighbor.RightChild;
                triangle.RightChild.LeftNeighbor = triangle.BaseNeighbor.LeftChild;

                triangle.BaseNeighbor.LeftChild.RightNeighbor = triangle.RightChild;
                triangle.BaseNeighbor.RightChild.LeftNeighbor = triangle.LeftChild;
            }

        }

        void RealSplit(BinaryTriangle triangle)
        {
            BinaryTriangle lc = triangle.GenLeftChild();
            BinaryTriangle rc = triangle.GenRightChild();

            triangle.LeftChild = lc;
            triangle.RightChild = rc;

            lc.LeftNeighbor = rc;
            rc.RightNeighbor = lc;

            lc.BaseNeighbor = triangle.LeftNeighbor;
            if (triangle.LeftNeighbor != null)
            {
                if (triangle.LeftNeighbor.BaseNeighbor == triangle)
                {
                    triangle.LeftNeighbor.BaseNeighbor = lc;
                }
                else if (triangle.LeftNeighbor.LeftNeighbor == triangle)
                {
                    triangle.LeftNeighbor.LeftNeighbor = lc;
                }
                else if (triangle.LeftNeighbor.RightNeighbor == triangle)
                {
                    triangle.LeftNeighbor.RightNeighbor = lc;
                }
                else
                {
                    // error
                }
            }

            rc.BaseNeighbor = triangle.RightNeighbor;
            if (triangle.RightNeighbor != null)
            {
                if (triangle.RightNeighbor.BaseNeighbor == triangle)
                {
                    triangle.RightNeighbor.BaseNeighbor = rc;
                }
                else if (triangle.RightNeighbor.LeftNeighbor == triangle)
                {
                    triangle.RightNeighbor.LeftNeighbor = rc;
                }
                else if (triangle.RightNeighbor.RightNeighbor == triangle)
                {
                    triangle.RightNeighbor.RightNeighbor = rc;
                }
                else
                {
                    // error
                }
            }
        }
        #endregion
        /*
        public void Draw(GraphicsDevice graphicsDevice, Matrix world, Matrix view, Matrix projection, Vector3 viewVector)
        {
            Matrix worldInverseTransposeMatrix = Matrix.Transpose(Matrix.Invert(world));

            if(vertexDeclaration == null)
            {
                vertexDeclaration = new VertexDeclaration(graphicsDevice, VertexPositionNormal.VertexElements);
            }

            Effect effect;

            for (int layer = 0; layer < effects.Length; ++layer)
            {

                if (nIndices[layer] == 0)
                    continue;

                //BasicEffect be = new BasicEffect(graphicsDevice, null);//kv.Value; 

                effect = effects[layer];

                graphicsDevice.VertexDeclaration = vertexDeclaration;
                graphicsDevice.Vertices[0].SetSource(vertexBuffer, 0, VertexPositionNormal.SizeInBytes);
                graphicsDevice.Indices = indexBuffers[layer];
                effect.Begin();
                //be.Begin();
                //be.World = world;
                //be.View = view;
                //be.Projection = projection;
                effect.Parameters["World"].SetValue(world);
                effect.Parameters["View"].SetValue(view);
                effect.Parameters["Projection"].SetValue(projection);
                //effect.Parameters["ViewVector"].SetValue(viewVector);
                effect.Parameters["WorldInverseTranspose"].SetValue(worldInverseTransposeMatrix);

                

                foreach (EffectPass pass in effect.CurrentTechnique.Passes)
                {
                    pass.Begin();

                    graphicsDevice.DrawIndexedPrimitives(PrimitiveType.TriangleList, 0, 0, nVertices, 0, nIndices[layer] / 3);
                    //graphicsDevice.DrawIndexedPrimitives(PrimitiveType.TriangleList, 0, 0, 3, 0, 1);
                    //graphicsDevice.DrawUserPrimitives(PrimitiveType.TriangleList, verticesa, 0, 1);
                    pass.End();
                }

                effect.End();
            }
        }
        */
        public void Draw(GraphicsDevice graphicsDevice, Matrix world, Matrix view, Matrix projection, Vector3 viewVector)
        {
            Matrix worldInverseTransposeMatrix = Matrix.Transpose(Matrix.Invert(world));

            if (vertexDeclaration == null)
            {
                vertexDeclaration = new VertexDeclaration(graphicsDevice, VertexPositionNormal.VertexElements);
            }

            graphicsDevice.VertexDeclaration = vertexDeclaration;
            graphicsDevice.Vertices[0].SetSource(vertexBuffer, 0, VertexPositionNormal.SizeInBytes);
            graphicsDevice.Indices = indexBuffer;
            
            effect.Begin();
            effect.Parameters["World"].SetValue(world);
            effect.Parameters["View"].SetValue(view);
            effect.Parameters["Projection"].SetValue(projection);
            effect.Parameters["WorldInverseTranspose"].SetValue(worldInverseTransposeMatrix);

            foreach (EffectPass pass in effect.CurrentTechnique.Passes)
            {
                pass.Begin();

                graphicsDevice.DrawIndexedPrimitives(PrimitiveType.TriangleList, 0, 0, nVertices, 0, nIndices / 3);
                pass.End();
            }

            effect.End();
        }

        //public VertexPositionNormal[] Vertices()
        //{
        //    VertexPositionNormal[] vertices = new VertexPositionNormal[width * height];
        //    for (int x = 0; x < width; ++x)
        //    {
        //        for (int y = 0; y < height; ++y)
        //        {
        //            vertices[Coordinate2Index(x, y)] = new VertexPositionNormal(new Vector3((x+offsetX)*scale, varianceTree.Heightmap.getHeight(x, y)*scale, (y+offsetY)*scale), Vector3.Zero);
        //        }
        //    }
        //    return vertices;
        //}

        public VertexPositionNormal[] VerticesCompressed()
        {
            bool[] usedVertices = UsedVertices();

            List<VertexPositionNormal> vertices = new List<VertexPositionNormal>();
            for (int i = 0; i < usedVertices.Length; ++i)
            {
                if (usedVertices[i])
                {
                    int x = i % width;
                    int y = i / width;
                    vertices.Add(new VertexPositionNormal(new Vector3((x + offsetX) * scale, varianceTree.Heightmap.getHeight(x, y) * scale, (y + offsetY) * scale), Vector3.Zero));
                }
            }
            return vertices.ToArray();
        }

        public int[] IndicesCompressed()
        {
            if (leftRoot != null)
            {
                List<int> leftIndices = GetIndices(leftRoot);
                List<int> rightIndices = GetIndices(rightRoot);

                int[] allIndices = leftIndices.Concat(rightIndices).ToArray();

                int[] usedVertexIndices = UsedVertexIndices();
                for (int i = 0; i < allIndices.Length; ++i)
                {
                    allIndices[i] = usedVertexIndices[allIndices[i]];
                }
                return allIndices;
            }
            else
            {
                return new int[0];
            }
        }

        public int[] Indices()
        {
            if (leftRoot != null)
            {
                List<int> leftIndices = GetIndices(leftRoot);
                List<int> rightIndices = GetIndices(rightRoot);

                int[] allIndices = leftIndices.Concat(rightIndices).ToArray();
                return allIndices;
            }
            else
            {
                return new int[0];
            }
        }

        //public int[] Indices()
        //{
        //    if (leftRoot != null)
        //    {
        //        List<int> leftIndices = GetIndices(leftRoot);
        //        List<int> rightIndices = GetIndices(rightRoot);
        //        return leftIndices.Concat(rightIndices).ToArray();
        //    }
        //    else
        //    {
        //        return new int[0];
        //    }
        //}

        List<int> GetIndices(BinaryTriangle triangle)
        {
            List<int> indices = new List<int>();
            if (triangle.IsSplit())
            {
                indices.AddRange(GetIndices(triangle.LeftChild));
                indices.AddRange(GetIndices(triangle.RightChild));
            }
            else
            {
                indices.Add(Coordinate2Index(triangle.Triangle.X1, triangle.Triangle.Y1));
                indices.Add(Coordinate2Index(triangle.Triangle.X2, triangle.Triangle.Y2));
                indices.Add(Coordinate2Index(triangle.Triangle.X3, triangle.Triangle.Y3));
            }

            return indices;
        }

        //public IDictionary<GolfCourseLayout.GolfCourseLayer, int[]> LayerIndices()
        //{
        //    IDictionary<GolfCourseLayout.GolfCourseLayer, int[]> dictionary = new Dictionary<GolfCourseLayout.GolfCourseLayer, int[]>();
        //    foreach (GolfCourseLayout.GolfCourseLayer layer in EnumHelper.GetEnumValues(typeof(GolfCourseLayout.GolfCourseLayer)))
        //    {
        //        if (leftRoot == null)
        //        {
        //            dictionary[layer] = new int[0];
        //        }
        //        else
        //        {
        //            List<int> leftIndices = GetIndices(leftRoot, layer);
        //            List<int> rightIndices = GetIndices(rightRoot, layer);
        //            dictionary[layer] = leftIndices.Concat(rightIndices).ToArray();
        //        }
        //    }
        //    return dictionary;
        //}

        //public IDictionary<GolfCourseLayout.GolfCourseLayer, int[]> LayerIndices()
        //{
        //    IDictionary<GolfCourseLayout.GolfCourseLayer, int[]> dictionary = new Dictionary<GolfCourseLayout.GolfCourseLayer, int[]>();
        //    int[] usedVertexIndices = UsedVertexIndices();
        //    foreach (GolfCourseLayout.GolfCourseLayer layer in EnumHelper.GetEnumValues(typeof(GolfCourseLayout.GolfCourseLayer)))
        //    {
        //        if (leftRoot == null)
        //        {
        //            dictionary[layer] = new int[0];
        //        }
        //        else
        //        {
        //            List<int> leftIndices = GetIndices(leftRoot, layer);
        //            List<int> rightIndices = GetIndices(rightRoot, layer);
        //            int[] allIndices = leftIndices.Concat(rightIndices).ToArray();
        //            for (int i = 0; i < allIndices.Length; ++i)
        //            {
        //                allIndices[i] = usedVertexIndices[allIndices[i]];
        //            }
        //            dictionary[layer] = allIndices;
        //        }
        //    }
        //    return dictionary;
        //}

        //List<int> GetIndices(BinaryTriangle triangle, GolfCourseLayout.GolfCourseLayer layer)
        //{
        //    List<int> indices = new List<int>();
            
        //    if (triangle.IsSplit())
        //    {
        //        indices.AddRange(GetIndices(triangle.LeftChild, layer));
        //        indices.AddRange(GetIndices(triangle.RightChild, layer));
        //    }
        //    else if(varianceTree.IsLayer(triangle.Triangle, layer))
        //    {
        //        indices.Add(Coordinate2Index(triangle.Triangle.X1, triangle.Triangle.Y1));
        //        indices.Add(Coordinate2Index(triangle.Triangle.X2, triangle.Triangle.Y2));
        //        indices.Add(Coordinate2Index(triangle.Triangle.X3, triangle.Triangle.Y3));
        //    }

        //    return indices;
        //}

        int Coordinate2Index(int x, int y)
        {
            return y * width + x;
        }
    }
}
